import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 22. Generate Parentheses 括号生成
 * https://leetcode.com/problems/generate-parentheses/
 */
class GenerateParentheses {

    private int n;
    private final List<String> ans = new ArrayList<>();
    private char[] pathC;
    private final List<Integer> path = new ArrayList<>(); // 记录左括号的下标


    /**
     * 方法：使用回溯算法生成所有有效的括号组合
     * 
     * Args:
     * n - 要生成的括号对数
     * 
     * Returns:
     * List<String> - 包含所有有效括号组合的列表
     * 
     * Time: O(4^n/√n) - 卡特兰数的时间复杂度
     * Space: O(n) - 递归调用栈的深度
     */
    public List<String> generateParenthesis(int n) {
        this.n = n;
        pathC = new char[n * 2]; // 所有括号长度都是一样的 n*2
        backtrack(0, 0);
        return ans;
    }

    // 目前填了 i 个括号
    // 这 i 个括号中有 open 个左括号，i-open 个右括号
    private void backtrack(int i, int open){
        if(i == n * 2){
            ans.add(new String(pathC));
            return;
        }
        if(open < n){
            pathC[i] = '(';
            backtrack(i + 1, open + 1);
        }
        if(i - open < open){
            pathC[i] = ')';
            backtrack(i + 1, open);
        }
    }

    

    /**
     * 方法：使用深度优先搜索生成所有有效的括号组合
     * 
     * Args:
     * n - 要生成的括号对数
     * 
     * Returns:
     * List<String> - 包含所有有效括号组合的列表
     * 
     * Time: O(4^n/√n) - 卡特兰数的时间复杂度
     * Space: O(n) - 递归调用栈的深度
     */
    public List<String> generateParenthesis1(int n) {
        this.n = n;
        dfs(0, 0);
        return ans;
    }

    // 目前填了 i 个括号
    // 这 i 个括号中的左括号个数 - 右括号个数 = balance
    private void dfs(int i, int balance) {
        if (path.size() == n) {
            char[] s = new char[n * 2];
            Arrays.fill(s, ')');
            for (int j : path) {
                s[j] = '(';
            }
            ans.add(new String(s));
            return;
        }
        // 枚举填 close=0,1,2,...,balance 个右括号
        for (int close = 0; close <= balance; close++) {
            // 先填 close 个右括号，然后填 1 个左括号，记录左括号的下标 i+close
            path.add(i + close);
            dfs(i + close + 1, balance - close + 1);
            path.remove(path.size() - 1);
        }
    }
}